package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月22日
*时间：上午10:54:44
*/
public class Q368 {
    /**
     * 1去括号 2先算*、/ 3算+、-
     * @param expression: an array of strings;
     * @return: an integer
     */
    public int evaluateExpression(String[] expression) {
        Stack<String> stack = new Stack<>();
        // 去括号
        for (String s : expression) {
            if (")".equals(s)) {
                List<String> list = new ArrayList<>();
                while (!stack.isEmpty()) {
                    String v = stack.pop();
                    if ("(".equals(v)) {
                        stack.push(headle(list));
                        break;
                    } else {
                        list.add(0, v);
                    }
                }
            } else {
                stack.add(s);
            }
        }
        List<String> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            list.add(0, stack.pop());
        }
        return Integer.parseInt(headle(list));
    }

    private String headle(List<String> list) {
        if (list.size() <= 0) {
            return "0";
        }
        boolean hasSymbol = true;
        while (hasSymbol) {
            hasSymbol = false;
            for (int i = 0; i < list.size(); i++) {
                String s = list.get(i);
                if ("*".equals(s) || "/".equals(s)) {
                    hasSymbol = true;
                    int a = Integer.parseInt(list.get(i - 1));
                    int b = Integer.parseInt(list.get(i + 1));
                    int rs = 0;
                    if ("*".equals(s)) {
                        rs = a * b;
                    } else {
                        rs = a / b;
                    }
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.add(i - 1, String.valueOf(rs));
                    break;
                }
            }
        }
        hasSymbol = true;
        while (hasSymbol) {
            hasSymbol = false;
            for (int i = 0; i < list.size(); i++) {
                String s = list.get(i);
                if ("+".equals(s) || "-".equals(s)) {
                    hasSymbol = true;
                    int a = Integer.parseInt(list.get(i - 1));
                    int b = Integer.parseInt(list.get(i + 1));
                    int rs = 0;
                    if ("+".equals(s)) {
                        rs = a + b;
                    } else {
                        rs = a - b;
                    }
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.add(i - 1, String.valueOf(rs));
                    break;
                }
            }
        }
        return list.get(0);
    }

    @Test
    public void testA() {
        // String expression[] = { "2", "*", "6", "-", "(", "23", "+", "7", ")", "/", "(", "1", "+", "2", ")" };
        // String expression[] = { "(", "(", "(", "(", "(", ")", ")", ")", ")", ")" };
        String expression[] = {};
        System.out.println(evaluateExpression(expression));
    }
}
